﻿#include <iostream>

#define MIN(a,b) (a<b?a:b)

static bool isPalindromicString(const char* str, const int start, const size_t count)
{
	if (!str) return false;

	int l = start;
	int r = start + count - 1;
	while (l <= r)
	{
		if (str[l++] != str[r--])
		{
			return false;
		}
	}

	return true;
}

/**
 * 暴力递归
 */
static int minCuttingCount(const char* str, const int index)
{
	auto strLen = strlen(str);
	if (index >= strLen) return 0;

	int minCount = 0x1fffffff;
	int cur;
	for (int i = index; i < strLen; i++)
	{
		if (isPalindromicString(str, index, i - index + 1))
		{
			if (i == strLen - 1)
			{
				cur = 0;
			}
			else
			{
				cur = 1 + minCuttingCount(str, i + 1);
			}

			minCount = MIN(minCount, cur);
		}
	}

	return minCount;
}

// 用于判断str i~j 是否回文的dp表
static bool* strPalindromicDp = nullptr;

/**
 * 使用dp表判断str从start开始数count个字符的子串是否是回文
 * @param start 从这个索引开始
 * @param count 子串一共多少个字符
 */
static bool isPalindromicStringByDp(const char* str, const int start, const size_t count)
{
	auto strLen = strlen(str);
	if (!strPalindromicDp)
	{
		strPalindromicDp = (bool*)malloc(strLen * strLen * sizeof(bool));
		memset(strPalindromicDp, 0, strLen * strLen * sizeof(bool));

		for (int i = 0; i < strLen; i++)
		{
			strPalindromicDp[i + i * strLen] = true;
			if (i < strLen - 1)
			{
				strPalindromicDp[i + 1 + i * strLen] = (str[i] == str[i + 1]);
			}
		}

		for (int i = strLen - 1 - 2; i >= 0; i--)
		{
			for (int j = i + 2; j < strLen; j++)
			{
				if (str[i] == str[j])
				{
					strPalindromicDp[j + i * strLen] = strPalindromicDp[j - 1 + (i + 1) * strLen];
				}
				else
				{
					strPalindromicDp[j + i * strLen] = false;
				}
			}
		}

		/*	printf("strPalindromicDp:\n");
			for (int i = 0; i < strLen; i++)
			{
				for (int j = 0; j < strLen; j++)
				{
					printf("%d ", strPalindromicDp[j + i * strLen] & 1);
				}

				printf("\n");
			}
			printf("\n");*/
	}

	int end = start + count - 1;
	return strPalindromicDp[end + start * strLen];
}

/**
 * minCuttingCount的严格表结构做法
 */
static int minCuttingCountByDp(const char* str)
{
	if (!str) return 0;

	auto strLen = strlen(str);
	if (strLen <= 1) return 0;

	int* dp = (int*)malloc(strLen * sizeof(int));
	memset(dp, 0, strLen * sizeof(int));

	int minCount;
	int cur;
	for (int index = strLen - 1; index >= 0; index--)
	{
		minCount = 0x1fffffff;
		for (int i = index; i < strLen; i++)
		{
			if (isPalindromicStringByDp(str, index, i - index + 1))
			{
				if (i == strLen - 1)
				{
					cur = 0;
				}
				else
				{
					cur = 1 + ((i + 1 < strLen) ? dp[i + 1] : 0);
				}

				minCount = MIN(minCount, cur);
			}
		}

		dp[index] = minCount;
	}

	int res = dp[0];
	free(dp);
	return res;
}

/**
 * 给定一个字符串str，返回把str全部切成回文子串的最小分割数。
 * 
 * 举例:
 * str="ABA", 不需要切割，str本身就是回文串，所以返回0.
 * str="ACDCDCDAD", 最少需要切2次变成3个回文子串，比如"A"、"CDCDC"和"DAD", 所以返回2.
 * 
 * 思路：
 * 从左到右尝试，从位置i到str.Length-1上，最少需要切几次?
 * 暴力递归时，从i开始往位置j之后进行尝试时，首先要确保从i到j的子串是回文，否则没有意义。
 * 改动态规划时，需要优化暴力递归中判断i~j是否回文的循环逻辑，否则时间复杂度将达到O(N^3)。
 这个判断循环的逻辑可以优化为范围尝试的查表法。

   举例：
             a   b   c   d   c   b   a
			 0   1   2   3   4   5   6   i
-----------------------------------------------
	 a   0 | T   F	 F	 F	 F	 F	 T
	 b   1 | X	 T   F	 F	 F	 T	 F
	 c   2 | X	 X	 T   F	 T	 F	 F
	 d   3 | X	 X	 X   T	 F   F	 F
	 c   4 | X	 X	 X	 X   T	 F   F
	 b   5 | X	 X	 X	 X   X   T	 F
	 a   6 | X	 X	 X	 X	 X   X   T
		 j |

	先填对角线：(0,0)->(1,1)->(2,2)->...->(6,6), 由于只有一个字符，故肯定是回文，填True。
	然后填(0,1)->(1,2)->(2,3)->...->(5,6), 如果str[i]==str[i+1]，则是回文，填True；否则不是回文，填False。
	对于普遍位置(i,j), 如果str[i]==str[j], 那么看(i-1,j-1)是否是True，如果是，则填True；反之填False。∴(i,j)的值依赖于其左下角的格子(i-1,j-1)

	有了这张表，在判断str从i~j是否是回文，就直接查表即可，不需要再循环遍历了。
 * 
 */
int main_minCuttingCountToPalindromicSubString()
{
	char str[] = "AABBBAA";
	int minCount = minCuttingCount(str, 0);
	printf("%d\n", minCount);
	
	minCount = minCuttingCountByDp(str);
	printf("%d", minCount);

	if (strPalindromicDp)
	{
		free(strPalindromicDp);
		strPalindromicDp = nullptr;
	}

	return 0;
}